// m

// 给定一个整数数组nums
// 要求：找到其中最长严格递增子序列的长度
// 说明： 子序列：由数组派生而来的序列，删除或者不删除数组中的元素不改变其余元素的顺序

// 解题思路： 动态规划
// 1. 划分阶段：按照子序列的结尾位置进行阶段划分
// 2. 定义状态：定义状态dp[i]表示为：以nums[i]结尾的最长递增子序列长度
// 3. 状态转移方程：一个较小的数后边如果出现一个较大的数，则会形成一个更长的递增子序列
//    对于满足0 <= j < i 的数组元素nums[i]和nums[j]来说
//    1），如果nums[j] < nums[i],则nums[i] 可以接在nums[j]后面，此时以nums[i]为结尾的最长递增子序列会在以nums[j]结尾的最长
//    递增子序列长度的基础上加1，即dp[i] = dp[j] + 1
//    2），如果nums[j] >= nums[i]，则nums[i]不可以接在nums[j]后面，可以直接跳过
// 综上，我们的状态转移方程为：dp[i] = max(dp[i], dp[j] + 1)，0 <= j < i， nums[j] < nums[i]
// 4. 初始条件，默认状态下，把数组中的每个元素都作为长度为1的递增子序列，即dp[i] = 1
// 5. 最终结果，根据我们之前定义的状态，dp[i]表示以nums[i]结尾的最长递增子序列长度，那为了计算出最大的最长递增子序列长度
// 则需要再遍历一遍dp数组，求出最大值即为最终结果

// 复杂度分析
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
function lengthOfLIS(nums) {
    let size = nums.length
    let dp = new Array(size).fill(1)

    for (let i = 0; i < size; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    let max = dp[0]
    for (let i = 0; i < size; i++) {
        if (dp[i] > max) {
            max = dp[i]
        }
    }
    return max
}

// 思路：

// 这种做法的主要目的是要使上升子序列的长度尽可能的长，序列的差尽可能的小，，就要使序列上升的速度尽可能的慢，让序列内末尾数字尽可能的小。从而可以获得更长的递增子序列，这是一种贪心算法的思想

// 维护一个result数组，用来存放单调递增序列结果，遍历数组
// 1. 如果`nums[i] > result[len - 1]`,直接push到末尾
// 2. 否则，在result数组中二分查找，找到第一个比`nums[i]`大的`result[j]`,更新result[j] = nums[i]
// 在放弃栈内容顺序正确性的情况下保证了栈长度的正确性
// 在没有替换完栈中的值时，栈中被替换的的值，起到的是占位的效果，为后面遍历数字提供参照的作用；

// https://segmentfault.com/a/1190000042360634?utm_source=sf-backlinks
function lengthOfLIS2(nums) {
    const n = nums.length
    if (n <= 1) return n;
    let result = [nums[0]]
    let len = result.length    // 最大长度
    for (let i = 1; i < n; i++) {
        if (nums[i] > result[len - 1]) { //大于末尾的值， 直接近栈
            result.push(nums[i])
            ++len
        } else {
            let left = 0, right = len;
            while (left < right) { // 二分查找序列内第一个大于nums[i]的值
                const mid = (left + right) >> 1
                if (result[mid] < nums[i]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            result[left] = nums[i] // 替换
        }
    }
    return len
}

// 最长上升子序列进阶：得到正确的序列
// 1. 将result修改为存储下标，（最后回溯是会改成真正的值）
// 2. 增加chain变量，存放每一位在被加入到result时其对应的前一位的下标值，进行关系绑定
// 3. 回溯chain，覆盖result的值。因为result内，最后一位一定是正确的，所以可以从后往前进行修正

function getOfLIS3(nums) {
    const n = nums.length
    if (n <= 1) return nums;
    let result = [0]  // 由原来存储具体值改为存储下标
    let chain = new Map() // 通过下标存储映射关系
    for (let i = 0; i < n; i++) {
        const j = result[result.length - 1]
        if (nums[i] > nums[j]) {
            chain.set(i, { val: i, pre: j })
            result.push(i)
        } else {
            let left = 0, right = result.length;
            while (left < right) {
                const mid = (left + right) >> 1
                if (nums[result[mid]] < nums[i]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            chain.set(i, { val: i, pre: result[left - 1] })
            result[left] = i
        }
    }
    let preIdx = result[result.length - 1]
    let len = result.length
    // 从后往前进行回溯，修正覆盖result中的值，找到正确的顺序
    while (chain.get(preIdx)) {
        let lastObj = chain.get(preIdx)
        result[--len] = nums[lastObj.val]
        preIdx = lastObj.pre
    }
    return result
};

// vue.js里的最长递增子序列实现， 用数组来实现插入result索引和上一个更新的索引之间的映射关系
function getSequence(arr) {
    const p = arr.slice() // 回溯专用
    const result = [0]
    let i, j, u, v, c
    const len = arr.length
    for (i = 0; i < len; i++) {
        const arrI = arr[i]
        // 排除了等于0的情况，原因是0并不代表任何dom元素，只是用来做占位的
        if (arrI !== 0) {
            j = result[result.length - 1]
            // 当前值大于子序列最后一项
            if (arr[j] < arrI) {
                // p内存储当前值的前一位下标
                p[i] = j
                // 存储当前值的下标
                result.push(i)
                continue
            }
            u = 0
            v = result.length - 1
            // 当前数值小于子序列最后一项时，使用二分法找到第一个大于当前数值的下标
            while (u < v) {
                c = ((u + v) / 2) | 0
                if (arr[result[c]] < arrI) {
                    u = c + 1
                } else {
                    v = c
                }
            }
            if (arrI < arr[result[u]]) {
                // 第一位不需要操作，因为它没有前一项
                if (u > 0) {
                    // p内存储找到的下标的前一位
                    p[i] = result[u - 1]
                }
                // 找到下标，直接替换result中的数值
                result[u] = i
            }
        }
    }
    u = result.length
    v = result[u - 1]
    // 回溯，从最后一位开始，将result全部覆盖，
    while (u-- > 0) {
        result[u] = v
        v = p[v]
    }
    return result
}

let arr = [2, 1, 5, 3, 6, 4, 8, 9, 7]
let arr2 = [10, 9, 2, 5, 3, 7, 1, 18]
console.log(lengthOfLIS(arr))
console.log(lengthOfLIS2(arr))
console.log(getOfLIS3(arr))
console.log(getSequence(arr))